//解法二：将每个罗马数看成单一的数
//如果前面的数小于后面的数字，就将前面的数取反
class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> hash_map{
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
        };

        int sum = 0;
        for (int i = 0; i < s.size() - 1; ++i)
        {
            int val = hash_map[s[i]];
            if (val < hash_map[s[i + 1]])
                sum -= val;
            else
                sum += val;
        }

        sum += hash_map[s.back()];


        return sum;
    }
};

//解法一：考虑组合
// class Solution {
// public:
//     int romanToInt(string s) {
//         unordered_map<char, int> hash_map{
//             {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000}
//         };

//         int sum = 0;
//         char prev = s[0];

//         for (int i = 1; i < s.size(); ++i)
//         {
//             char ch = s[i];
//             if (hash_map[ch] > hash_map[prev])
//             {
//                 sum += hash_map[ch] - hash_map[prev];

//                 ++i;
//                 if (i >= s.size())
//                     return sum;

//                 prev = s[i];
//             }
//             else
//             {
//                 sum += hash_map[prev];
//                 prev = s[i];
//             }
//         }

//         sum += hash_map[prev];

//         return sum;
//     }
// };




class Solution {
public:
    string intToRoman(int num) {
        string ret;
        unordered_map<int, char> hash_map{
            {1, 'I'}, {5, 'V'}, {10, 'X'}, {50, 'L'}, {100, 'C'}, {500, 'D'}, {1000, 'M'}
        };
        
        int power = 1000;
        while (power > 0)
        {
            int temp = num / power * power;
            if (temp == 4 * power || temp == 9 * power)
            {
                ret += hash_map[power];
                ret += hash_map[temp + power];
            }
            else
            {
                if (temp < 5 * power)
                    ret += string(temp / power, hash_map[power]);
                else
                {
                    temp -= 5 * power;
                    ret += hash_map[5 * power];
                    ret += string(temp / power, hash_map[power]);
                }
            }

            num %= power;
            power /= 10;
        }

        return ret;   
    }
};

class Solution {
public:
    int lengthOfLastWord(string s) {
        int index = s.size() - 1;
        while (index >= 0 && s[index] == ' ')        
            --index;

        int begin = index;
        while (begin >= 0 && s[begin] != ' ')
            --begin;

        return index - begin;
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string min_str = strs[0];
        for (auto& str : strs)
            min_str = min_str.size() > str.size() ? str : min_str;

        for (int i = 0; i < min_str.size(); ++i)
        {
            char ch = strs[0][i];
            bool flag = true;
            for (int j = 1; j < strs.size(); ++j)
            {
                if (ch != strs[j][i])
                {
                    flag = false;
                    break;
                }
            }

            if (!flag)
                return strs[0].substr(0, i);
        }

        return min_str;
    }
};

class Solution {
private:
    void reverse(string& str, int begin, int end)
    {
        while (begin < end)
        {
            std::swap(str[begin], str[end]);

            ++begin;
            --end;
        }
    }
public:
    string reverseWords(string s) {
        //找到最后一个字母
        int end = s.size() - 1;
        while (end >= 0 && s[end] == ' ')
            --end;

        //找到第一个字母
        int begin = 0;
        while (begin <= end && s[begin] == ' ')  
            ++begin;

        //去除[begin, end]中的重复空格
        int slow = begin, fast = begin + 1;
        for (; fast <= end; ++fast)
        {
            if (s[fast] != ' ' || s[slow] != ' ')
                s[++slow] = s[fast];
        }

        //将[begin, slow]的字符放到最前面
        int cur = 0;
        for (int i = begin; i <= slow; ++i)
            s[cur++] = s[i];

        //缩容
        s.resize(cur);

        //开始反转
        reverse(s, 0, s.size() - 1);

        int prev = 0;
        for (int fast = 0; fast < s.size(); ++fast)
        {
            if (s[fast] == ' ')
            {
                reverse(s, prev, fast - 1);
                prev = fast + 1;
            }
        }
        reverse(s, prev, s.size() - 1);

        return s;
    }
};